1. Field of The Invention
This disclosure relates to memory management units, in particular memory management units containing a look-aside buffer used to speed up translation in a computer system supporting virtual memory, and in particular, to methods for preventing and recovering from a situation where multiple translations in the buffer correspond to the same address. In addition, this disclosure relates to a particular data structure used to store translations, i.e. a B-tree, that is accessed when a requested translation is not present in the look-aside buffer.
2. Technical Background of the Invention
In computers supporting a virtual memory system, the address space to which programs refer is called "virtual memory" and each virtual address specified by a program instruction is translated by the memory management unit (MMU) to a physical or real address which is passed to the main memory subsystem (hereinafter referred to as "memory") in order to retrieve the accessed item. The use of virtual memory permits the size of programs to greatly exceed the size of the physical memory and provides flexibility in the placement of programs in the physical memory. For various reasons, including the need to keep tables required for address translation to a reasonable size, some virtual to real address translation schemes effect translation in two or more stages.
Usually, each stage of the translation requires one or more accesses to a table that is held in memory. In order to reduce the total number of memory accesses required per address translation, one or more translation-lookaside buffers (TLBs) are often provided in the MMU to reduce the average time required to effect a corresponding number of steps in the address translation scheme. A TLB is a cache-like memory, typically implemented in Static Random Accessible Memory (SRAM) and/or Content Addressible Memory (CAM), that holds translations corresponding to a particular stage of the translation scheme that have been recently fetched from memory.
Access to a TLB entry holding an output address corresponding to an input address obviates the need for and is typically many orders of magnitude faster than access to the in-memory table in order to retrieve the output address corresponding to the input address. (A TLB entry may contain fields describing the translation, in addition to an input and output address fields, such as a protection field. Furthermore, one or more fields used to determine the output address, instead of the output address itself, may be stored in the TLB entries.)
If the TLB does not contain the requested translation (i.e. upon a TLB "miss") then the MMU initiates a search of translation tables stored in memory for the requested translation and then loads it into the TLB, where it may be available for subsequent fast access should translation for the same input address be required at some future point. The part of the MMU performing this function, in hardware (logic circuitry), is hereinafter referred to as the "table walker".
Due to errors of various sorts such as soft errors in RAM, hardware transient errors and software errors, two or more translations for the same input address may appear in the TLB. It would be desirable for the MMU to detect that two or more translations exist in the TLB for the specified input address to be translated and to be able to recover from this anomalous situation by taking appropriate action such as invalidating the two or more translations and initiating a search by the table walker.
The input address range for the input to a particular stage of the address translation scheme in a computer system supporting virtual memory may be extremely large. For example, in a 64-bit workstation sold by HaL Computer Systems, Inc. (assignee of this disclosure), a 51 bit address is translated in the first stage. A simple array with one entry for each possible input address, as commonly used in the prior art (e.g. page table), is not a feasible solution, in terms of memory requirements, for implementing the translation table for such a large input address range.
Known data structures to implement the translation table have memory requirements proportional to the total number of possible input addresses rather than the number of input addresses that have been translated, and thus are not practical for very large input address spaces.